package ru.amse.stroganova.algorythms;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import ru.amse.stroganova.graph.AbstractGraph;
import ru.amse.stroganova.graph.Edge;
import ru.amse.stroganova.graph.Vertex;

/**
 * This class presentas topological sort for DAGs. If graph has loops can return one of them.
 * 
 * @author Dasha Stroganova
 *
 */
public class TopologicalSort {
	private final List<Vertex> sortedVertices;
	
	private final List<Edge> loopEdges;
	
	private boolean isLoopProccessing;
	
	private enum Color{/***/WHITE, /***/GRAY, /***/BLACK};
	
	private final Color[] wasVisited;
	
	private final List<Vertex> vertices;
	
	private int loopStart;
	
	private static final String ERROR_MESSAGE = "Cannot find topological sort of the given graph - it has a loop.";
	
	/**
	 * Creates new topological sort on this graph.
	 * 
	 * @param graph
	 */
	public TopologicalSort(AbstractGraph graph) {
		sortedVertices = new LinkedList<Vertex>();
		loopEdges = new LinkedList<Edge>();
		isLoopProccessing = false;
		vertices = new ArrayList<Vertex>(graph.getVertices());
		wasVisited = new Color[graph.getVertices().size()];
		for (int i = 0; i < wasVisited.length; i++) {
			wasVisited[i] = Color.WHITE;
		}

		for (int vertexNum = 0; vertexNum != -1; vertexNum = getNextUnvisitedVertex()) {
			if (vertices.size() == 0) {
				break;
			}
			if (!hasLoops()) {
				dfs(vertices.get(vertexNum));
			} else {
				break;
			}
		}
		
		if (hasLoops()) {
			sortedVertices.clear();
		}
	}
	
	/**
	 * Checks whether graph has loops.
	 * 
	 * @return true if it does; false otherwise
	 */
	public boolean hasLoops() {
		return !loopEdges.isEmpty();
	}
	
	/**
	 * Returns list of sorted vertices in right order if graph was DAG. Throws exception otherwise.
	 * 
	 * @return list of vertices
	 */
	public List<Vertex> getSortedVertices() {
		if (hasLoops()) {
			throw new IllegalStateException("Graph has loops: there are no sorted vertices");
		}
		return sortedVertices;
	}
	
	/**
	 * Returns list of edges making loop. Throws {@link IllegalStateException} if graph is DAG
	 * 
	 * @return list of loop edges
	 */
	public List<Edge> getLoop() {
		if (!hasLoops()) {
			throw new IllegalStateException("This graph has no loops.");
		}
		return loopEdges;
	}
	
	/**
	 * If any errors exist return error message.
	 * 
	 * @return error message if error exists; empty string otherwise
	 */
	public String getErrorMessage() {
		if (hasLoops()) {
			return ERROR_MESSAGE;
		}
		return "";
	}
	
	private int getNextUnvisitedVertex() {
		for (int i = 0; i < wasVisited.length; i++) {
			if (wasVisited[i] == Color.WHITE) {
				return i;
			}
		}
		return -1;
	} 
	
	private void dfs(Vertex vertex) {
		if (hasLoops()) {
			return;
		}
		int vertexIndex = vertices.indexOf(vertex);
		wasVisited[vertexIndex] = Color.GRAY;
		for (Edge edge : vertex.getOutgoingEdges()) {
			Vertex opposite = edge.getOppositeVertex(vertex);
			int oppositeIndex = vertices.indexOf(opposite);
			if (wasVisited[oppositeIndex] == Color.WHITE) {
				dfs(opposite);
				if (isLoopProccessing) {
					loopEdges.add(0, edge);
					if (vertexIndex == loopStart) {
						isLoopProccessing = false;
					}
					return;
				}
			} else if (wasVisited[oppositeIndex] == Color.GRAY) {
				isLoopProccessing = true;
				loopStart = oppositeIndex;
				loopEdges.add(0, edge);
				return;
			}
		}
		wasVisited[vertexIndex] = Color.BLACK;
		sortedVertices.add(0, vertex);
	}
}
